package com.cqs.leetcode.dp;

import com.cqs.leetcode.ds.ArraysUtils;
import com.google.common.base.Stopwatch;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

/**
 * @author lixqw
 * @date 2020/8/22
 */
public class SubarraySumEqualsK560 {

    /**
     * 暴力解法
     * 时间复杂度O(n^2)
     *
     * @param nums
     * @param k
     * @return
     */
    public int subarraySum(int[] nums, int k) {
        int result = 0;
        for (int i = 0; i < nums.length; ++i) {
            int sum = 0;
            for (int j = i; j < nums.length; ++j) {
                sum += nums[j];
                if (sum == k) {
                    ++result;
                }
            }
        }
        return result;
    }

    static class Solution {
        public int subarraySum(int[] nums, int k) {
            if (nums.length == 0) return 0;
            //sum[i] 表示前i个元素的和
            int[] sum = new int[nums.length];
            sum[0] = nums[0];
            for (int i = 1; i < nums.length; i++) {
                sum[i] = sum[i - 1] + nums[i];
            }
            Map<Integer, Integer> fre = new HashMap<>();
            //主要 初始化
            fre.put(0, 1);
            Integer total = 0;
            for (int i = 0; i < sum.length; i++) {
                //从sum[0]...sum[i-1]找大小为sum[i] - k的数
                int t = sum[i] - k;
                //sum[0]...sum[i-1] 出现了多少次（ sum[i] - k）
                Integer c = fre.getOrDefault(t, 0);
                total += c;
                Integer orDefault = fre.getOrDefault(sum[i], 0);
                //统计sum[i]出现的次数
                fre.put(sum[i], orDefault + 1);
            }
            return total;
        }
    }

    public static void main(String[] args) {
        while (true) {
            SubarraySumEqualsK560 sub = new SubarraySumEqualsK560();
            Solution solution = new Solution();
            int[] test = new int[500];
            for (int i = 0; i < test.length; i++) {
                test[i] = new Random().nextInt(10);
                if (new Random().nextFloat() > 0.5) {
                    test[i] = test[i] * -1;
                }
            }
//        test = new int[]{-3,3,8,1,5};
//            ArraysUtils.print(test);

            int k = new Random().nextInt(10);
//            k = 9;
            Stopwatch stopwatch = Stopwatch.createStarted();
            int i = sub.subarraySum(test, k);
            stopwatch.stop();
            int i1 = solution.subarraySum(test, k);
            //System.out.println(i + "\t"+ i1  + "\t" + stopwatch.elapsed());
            if (i != i1) {
                ArraysUtils.print(test);
                System.out.println(i + "\t" + i1 + "\t" + stopwatch.elapsed() + "\t" + k);
                break;
            }
        }


    }
}
